/**
 * 
 */

/**
 * @author zhongfang
 *
 */
public class 取数组中的最大和 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int v[]={1,5,2,3};
		int n=v.length;
		int[][] dp=new int[n][n];//面临[i][j]时候能取到的最大值
		boolean[][] from=new boolean[n][n];//面临[i][j]时候是否从头取
		for (int i = n-1; i >=0; i--) {
			dp[i][i]=v[i];
			System.out.println(i+" "+i+" "+dp[i][i]);
			for (int j = i+1; j < n; j++) {
				int tmp1=v[i]+(from[i+1][j]?i>=n-2?0:dp[i+2][j]:(i>=n-1||j==0)?0:dp[i+1][j-1]);
				int tmp2=v[j]+(from[i][j-1]?(i>=n-1||j==0)?0:dp[i+1][j-1]:j<2?0:dp[i][j-2]);
				if(tmp1>tmp2){//-------------------------等号，怎么取？
					from[i][j]=true;//从头取
					dp[i][j]=tmp1;
				}else {
					from[i][j]=false;//从尾取
					dp[i][j]=tmp2;
				}
				System.out.println(i+" "+j+" "+dp[i][j]);
			}
		}
		System.out.println(dp[0][n-1]>=(from[0][n-1]?dp[1][n-1]:dp[0][n-2]));
	}

}
